|
In combinatorial game theory, the Sprague–Grundy theorem states that every impartial game under the normal play convention is equivalent to a nimber. The Grundy value or nim-value of an impartial game is then defined as the unique nimber that the game is equivalent to. In the case of a game whose positions (or summands of positions) are indexed by the natural numbers (for example the possible heap sizes in nim-like games), the sequence of nimbers for successive heap sizes is called the nim-sequence of the game. The theorem and its proof encapsulate the main results of a theory discovered independently by R. P. Sprague (1935) and P. M. Grundy (1939).() ==Definitions== For the purposes of the Sprague–Grundy theorem, a ''game'' is a two-player game of perfect information satisfying the ''ending condition'' (all games come to an end: there are no infinite lines of play) and the ''normal play condition'' (a player who cannot move loses). An ''impartial game'' is one such as nim, in which each player has exactly the same available moves as the other player in any position. Note that games such as tic-tac-toe, checkers, and chess are ''not'' impartial games. In the case of checkers and chess, for example, players can only move their own pieces, not their opponent's pieces. And in tic-tac-toe, one player puts down X's, while the other puts down O's. Positions in impartial games fall into two ''outcome classes'': either the next player (the one whose turn it is) wins (an ''N-position'') or the previous player wins (a ''P-position''). In this proof, a position is identified with the set of positions that can be reached in one move (these positions are called ''options''). For example, the position is a P-position under normal play, because the current player has no moves and therefore loses. The position , in contrast, is an N-position; the current player has only one option, and that option is a losing position for their opponent. A ''nimber'' is a special position denoted for some ordinal . is , the P-position given as an example earlier. The other nimbers are defined inductively by ; in particular, (the example N-position from above), (a choice between the two example positions), etc. therefore corresponds to a heap of counters in the game of nim, hence the name. Two positions and can be ''added'' to make a new position in a combined game where the current player can choose either to move in or in . Explicit computation of the set is by repeated application of the rule , which incidentally indicates that position addition is both commutative and associative as expected. Two positions and are defined to be ''equivalent'' if for every position , the position is in the same outcome class as . Such an equivalence is written . 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Sprague–Grundy theorem」の詳細全文を読む スポンサード リンク
|